Mycobacterium tuberculosis (Mtb) is the leading cause of death from infection worldwide. Intradermal (ID) vaccination with BCG has variable efficacy against pulmonary tuberculosis, the major cause of mortality and disease transmission. We showed that the route and dose of BCG vaccination alters circulating and lung resident T cells and subsequent protection against Mtb challenge in nonhuman primates (NHP). NHP immunized with BCG by the intravenous (IV) route induced substantially higher antigen-specific CD4 (Th1 or Th17) and CD8 responses in blood, spleen, bronchoalveolar lavage (BAL), and lung lymph nodes compared to the same BCG dose administered by ID or aerosol (AE) routes. Moreover, IV immunization was the only route that induced a high frequency of antigen-specific tissue resident T cells in lung parenchyma. Six months after BCG vaccination, NHP were challenged with virulent Mtb. Strikingly, 9 of 10 NHP that received BCG IV were highly protected, with 6 NHP showing no detectable infection as determined by PET CT imaging, mycobacterial growth, pathology, granuloma formation, or de novo immune responses to Mtb-specific antigens. The finding that BCG IV prevents or significantly limits Mtb infection in NHP has important implications for vaccine development and provides a model for determining immune correlates and mechanisms of protection against Mtb.